Context Free Grammar
Q11.
A CFG (Context Free Grammar) is said to be in Chomsky Normal Form (CNF), if all the productions are of the form \mathrm{A} \rightarrow \mathrm{BC} or \mathrm{A} \rightarrow \mathrm{a}. Let G be a CFG in CNF. To derive a string of terminals of length x, the number of products to be used is:Q12.
Consider the following context-free grammars: G1: S\rightarrowaS|B, B\rightarrowb|bB G2: S\rightarrowaA|bB, A\rightarrowaA|B|\varepsilon, B\rightarrowbB|varepsilon Which one of the following pair of languages is generated by G1 and G2, respectively?Q14.
A CFG G is given with the following productions where S is the start symbol, A is a non-terminal and a and b are terminals.\begin{array}{l} S \rightarrow a S \mid A \\ A \rightarrow a A b|b A a| \epsilon \end{array}For the string "aabbaab" how many steps are required to derive the string and how many parse trees are there?Q15.
Consider a CFG with the following productions. S \to AA \mid B A \to 0A \mid A0 \mid 1 B \to 0B00 \mid 1 S is the start symbol, A and B are non-terminals and 0 and 1 are the terminals. The language generated by this grammar is:Q17.
A CFG G is given with the following productions where S is the start symbol, A is a non-terminal and a and b are terminals.\begin{array}{l} S \rightarrow a S \mid A \\ A \rightarrow a A b|b A a| \epsilon \end{array}Which of the following strings is generated by the grammar above?Q18.
Which of the following statements about parser is/are CORRECT? I. Canonical LR is more powerful than SLR. II. SLR is more powerful than LALR III. SLR is more powerful than Canonical LR.Q19.
Identify the language generated by the following grammar, where S is start variable. S\rightarrow XY X\rightarrow aX|a Y \rightarrowaYb|\inQ20.
In the context-free grammar below, S is the start symbol, a and b are terminals, and \epsilon denotes the empty string. S \to aSAb \mid \epsilon A \to bA \mid \epsilon The grammar generates the language